package l.l.w.leetcode._047PermutationsII;

import java.util.*;

/**
 * Created by llw on 2017/11/12.
 */
public class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if(nums==null || nums.length==0) return res;
        boolean[] used = new boolean[nums.length];
        List<Integer> list = new ArrayList<Integer>();
        Arrays.sort(nums);
        dfs(nums, used, list, res);
        return res;
    }

    public void dfs(int[] nums, boolean[] used, List<Integer> list, List<List<Integer>> res){
        if(list.size()==nums.length){
            res.add(new ArrayList<Integer>(list));
            return;
        }
        for(int i=0;i<nums.length;i++){
            if(used[i]) continue;
            if(i>0 &&nums[i-1]==nums[i] && !used[i-1]) continue;
            used[i]=true;
            list.add(nums[i]);
            dfs(nums,used,list,res);
            used[i]=false;
            list.remove(list.size()-1);
        }
    }

    public static void main(String[] args) {
        int[] a = {-1,2,0,-1,1,0,1};
        List<List<Integer>> result = new Solution().permuteUnique(a);
        System.out.println(result.size());
        System.out.println(result);
//        Collections.sort(result, new Comparator<List<Integer>>() {
//            @Override
//            public int compare(List<Integer> o1, List<Integer> o2) {
//                for(int i = 0; i < o1.size(); ++i){
//                    if(o1.get(i)>o2.get(i))return 1;
//                    else if(o1.get(i) < o2.get(i)) return -1;
//                    else continue;
//                }
//                return 0;
//            }
//        });
//        for(int i = 0; i < result.size(); ++i){
//            System.out.println(result.get(i));
//        }
    }
}
